package com.leetcode.algorithm.y20.m12;

/**
 * leetcode-cn.com
 * (done)912. 排序数组
 * @author jie.deng
 * @date 2020/12/24
 */
public class MySolution1224 {
    /**
     * 912. 排序数组
	 * 给你一个整数数组 nums，请你将该数组升序排列。
	 * 
	 * 示例 1：
	 * 
	 * 输入：nums = [5,2,3,1]
	 * 输出：[1,2,3,5]
	 * 示例 2：
	 * 
	 * 输入：nums = [5,1,1,2,0,0]
	 * 输出：[0,0,1,1,2,5]
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= nums.length <= 50000
	 * -50000 <= nums[i] <= 50000
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/sort-an-array
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param nums
     * @return
     */
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    
    private void quickSort(int[] arr, int fromIdx, int toIdx) {
        if (fromIdx >= toIdx) {
            return;
        }
        int l = fromIdx;
        int r = toIdx;

        // 第一步，选择一个值作为基准值
        int pivot = arr[l];

        // 第二步，partition操作:将小于基准值的元素放在基准值的前面，将大于基准值的元素放在基准值的后面。
        while (l < r) {
            // 将小于基准值的元素放在基准值的前面
            while (arr[r] >= pivot && l < r) {
                r--;
            }
            if (l >= r) {
                break;
            }
            arr[l++] = arr[r];

            // 将大于基准值的元素放在基准值的后面
            while (arr[l] <= pivot && l < r) {
                l++;
            }
            if (l >= r) {
                break;
            }
            arr[r--] = arr[l];
        }
        arr[r] = pivot;

        // 第三步，是对基准值的左右两侧，递归地进行第一步和第二步
        quickSort(arr, fromIdx, r - 1);
        quickSort(arr, r + 1, toIdx);
    }
    
    
    // 优化一：单边递归优化
    // 优化二：基准值选取优化
    // 优化三：partition 操作优化
    private void quickSort1(int[] arr, int fromIdx, int toIdx) {
        // TODO
    }
    
    
}
